//
// Created by francklinson on 2021/5/22.
//
#include <vector>
#include <iostream>
#include <queue>

using namespace std;

class Solution {

public:

    int furthestBuilding(vector<int> &heights, int bricks, int ladders) {
        int n = (int) heights.size();
        priority_queue<int, vector<int>, greater<>> pq;//小堆顶 这里面存的是要用梯子的
        int brickCost = 0; // 耗费的砖头数量
        for (int i = 1; i < n; ++i) {
            int jump = heights[i] - heights[i - 1];  // 跳跃的高度
            if (jump <= 0) continue;  // 比前面的一栋建筑矮，不需要跳跃
            pq.push(jump); // 入队
            if (pq.size() > ladders) {
                brickCost += pq.top();
                pq.pop();
            }
            if (brickCost > bricks) return i - 1; // 到不了i
        }
        return n - 1;
    }
};

int main() {
    vector<int> h{4, 2, 7, 6, 9, 14, 12};
    vector<int> h2{14, 3, 19, 3};
    vector<int> h3{4, 12, 2, 7, 3, 18, 20, 3, 19};
    Solution sol;
    cout << sol.furthestBuilding(h, 5, 1) << endl;
    cout << sol.furthestBuilding(h2, 17, 0) << endl;
    cout << sol.furthestBuilding(h3, 10, 2) << endl;
    return 0;
}
